//Suppose we have a file system that stores both files and directories. An examp
//le of one system is represented in the following picture: 
//
// 
//
// Here, we have dir as the only directory in the root. dir contains two subdire
//ctories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory
// subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file f
//ile2.ext. 
//
// In text form, it looks like this (with ⟶ representing the tab character): 
//
// 
//dir
//⟶ subdir1
//⟶ ⟶ file1.ext
//⟶ ⟶ subsubdir1
//⟶ subdir2
//⟶ ⟶ subsubdir2
//⟶ ⟶ ⟶ file2.ext
// 
//
// If we were to write this representation in code, it will look like this: "dir
//
//\tsubdir1
//\t\tfile1.ext
//\t\tsubsubdir1
//\tsubdir2
//\t\tsubsubdir2
//\t\t\tfile2.ext". Note that the '
//' and '\t' are the new-line and tab characters. 
//
// Every file and directory has a unique absolute path in the file system, which
// is the order of directories that must be opened to reach the file/directory its
//elf, all concatenated by '/'s. Using the above example, the absolute path to fil
//e2.ext is "dir/subdir2/subsubdir2/file2.ext". Each directory name consists of le
//tters, digits, and/or spaces. Each file name is of the form name.extension, wher
//e name and extension consist of letters, digits, and/or spaces. 
//
// Given a string input representing the file system in the explained format, re
//turn the length of the longest absolute path to a file in the abstracted file sy
//stem. If there is no file in the system, return 0. 
//
// 
// Example 1: 
//
// 
//Input: input = "dir
//\tsubdir1
//\tsubdir2
//\t\tfile.ext"
//Output: 20
//Explanation: We have only one file, and the absolute path is "dir/subdir2/file
//.ext" of length 20.
// 
//
// Example 2: 
//
// 
//Input: input = "dir
//\tsubdir1
//\t\tfile1.ext
//\t\tsubsubdir1
//\tsubdir2
//\t\tsubsubdir2
//\t\t\tfile2.ext"
//Output: 32
//Explanation: We have two files:
//"dir/subdir1/file1.ext" of length 21
//"dir/subdir2/subsubdir2/file2.ext" of length 32.
//We return 32 since it is the longest absolute path to a file.
// 
//
// Example 3: 
//
// 
//Input: input = "a"
//Output: 0
//Explanation: We do not have any files, just a single directory named "a".
// 
//
// Example 4: 
//
// 
//Input: input = "file1.txtfile2.txtlongfile.txt"
//Output: 12
//Explanation: There are 3 files at the root directory.
//Since the absolute path for anything at the root directory is just the name it
//self, the answer is "longfile.txt" with length 12.
// 
//
// 
// Constraints: 
//
// 
// 1 <= input.length <= 104 
// input may contain lowercase or uppercase English letters, a new line characte
//r '
//', a tab character '\t', a dot '.', a space ' ', and digits. 
// 
// 👍 76 👎 0


package leetcode.editor.cn;

//Java：Longest Absolute File Path
 class P388LongestAbsoluteFilePath{
    public static void main(String[] args) {
        Solution solution = new P388LongestAbsoluteFilePath().new Solution();
        // TO TEST
        System.out.println(solution.lengthLongestPath("file1.txtfile2.txtlongfile.txt"));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

        public int lengthLongestPath(String input) {
            if(input==null||input.length()==0) {
                return 0;
            }
            String[] words=input.split("\n");
            int[] pathLens=new int[words.length+1];//pathLens[i]存放地i层次的最后面的元素的路径长度
            pathLens[0]=-1;//层次最少是1，为了统一dp操作（具体看下面循环体），取pathLens[0]=-1
            int ans=0;
            //自左向右，dp
            for(String word:words){
                int level=word.lastIndexOf('\t')+1+1;//层次计算
                int nameLen=word.length()-(level-1);//计算名字长度
                //word的父文件夹必定目前是level-1层次的最后一个，因此pathLens[level-1]就是父文件夹路径长度
                //这个word必然是目前本层次的最后一个，因此需要刷新pathLens[level],+1是因为要加一个'\'
                pathLens[level]=pathLens[level-1]+1+nameLen;
                //如果是文件，还需要用路径长度刷新ans
                if(word.contains(".")) ans=Math.max(ans,pathLens[level]);
            }
            return ans;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}